//给定一棵有 n 个结点的二叉树，你的任务是检查是否可以通过去掉树上的一条边将树分成两棵，且这两棵树结点之和相等。 
//
// 样例 1: 
//
// 输入:     
//    5
//   / \
//  10 10
//    /  \
//   2   3
//
//输出: True
//解释: 
//    5
//   / 
//  10
//      
//和: 15
//
//   10
//  /  \
// 2    3
//
//和: 15
// 
//
// 
//
// 样例 2: 
//
// 输入:     
//    1
//   / \
//  2  10
//    /  \
//   2   20
//
//输出: False
//解释: 无法通过移除一条树边将这棵树划分成结点之和相等的两棵子树。
// 
//
// 
//
// 注释 : 
//
// 
// 树上结点的权值范围 [-100000, 100000]。 
// 1 <= n <= 10000 
// 
//
// 
//
// Related Topics 树 深度优先搜索 二叉树 👍 56 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func checkEqualTree(root *TreeNode) bool {
var dfs func(root *TreeNode) int
var stack []int
dfs = func(root *TreeNode) int {
if root == nil {
return 0
}

if root.Left == nil && root.Right == nil {
return root.Val
}

left := dfs(root.Left)
right := dfs(root.Right)
stack = append(stack, root.Val+left+right)
return root.Val + left + right
}
sum := dfs(root)
stack = stack[:len(stack)-1]
if sum%2 == 0 {
for i := 0; i < len(stack); i++ {
if stack[i] == sum/2 {
return true
}
}
}
return false
}

//leetcode submit region end(Prohibit modification and deletion)
